package arithmetic.demo17;

/**
 * 动态规划： 区间dp + 分类讨论 + 空串初始化： 通配符匹配
 */
class Solution {
    public boolean isMatch(String s, String p) {
        // 长度
        int len1 = p.length(), len2 = s.length();

        // 创建 dp
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];

        // 初始化
        s = " " + s;
        p = " " + p;
//        空格对空格肯定相等所以先置为 true
        dp[0][0] = true;
        for (int i = 1; i <= len1; i++) {
            // 如果 p 的位置为 * 是可以匹配空格的 需要置为 true
            if (p.charAt(i) == '*') {
                dp[i][0] = true;
            } else {
                // 如果遇到 非空串了就不能匹配空串了 
                // 直接跳出 后面的也不能匹配了
                break;
            }

        }

        // 自上而下， 自左而右填表
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                // 如果遇到 * 就直接返回true
                char ch = p.charAt(i);
                if ((ch == s.charAt(j) || ch == '?') && dp[i - 1][j - 1]) {
                    // 如果相等就看前面的字符是否相等
                    dp[i][j] = true;
                } else if (ch == '*' && (dp[i - 1][j] || dp[i][j - 1])) {
                    // 继承前面的是否相等
                    dp[i][j] = true;
                }
            }
        }

        // 确定最终返回值
        return dp[len1][len2];
    }
}

class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isMatch("aa", "*"));
    }
}

/**
 * 动态规划： 区间dp + 分类讨论 + 保留自身匹配下一个 + 空串 ： 正则表达式匹配
 */

class Solution2 {
    public boolean isMatch(String s, String p) {
        // 动态规划思想 + 分类讨论 + 空串初始化
        int len1 = s.length(), len2 = p.length();

        // 创建dp
        boolean[][] dp = new boolean[len1+1][len2+1];

        // 初始化
        s = " " + s;
        p = " " + p;
        // 转化为字符数组来整理
        char[] str = s.toCharArray();
        char[] ptr = p.toCharArray();
        // 先匹配空格 对应 空格
        dp[0][0] = true;
        for(int j = 2; j <= len2; j+= 2) {
            if(ptr[j] == '*') {
                // 如果一开始有通配符 _*
                // _* 可以匹配空串 所以我们置为 true
                dp[0][j] = true;
            } else {
                // 只要一遇到非通配符下面就无法匹配了
                break;
            }
        }

        // 自上而下, 自左而右的填表
        for(int i = 1; i <= len1; i++) {
            for(int j =1; j <= len2; j++) {
                if(ptr[j] == str[i] || ptr[j] == '.' ) {
                    // 如果两个字符相等 或者 p 位置为 . 时
                    // 就看上一个位置是否相等
                    dp[i][j] = dp[i-1][j-1];
                } else if(ptr[j] == '*') {
                    if( ((ptr[j-1] == '.' || str[i] == ptr[j-1]) && dp[i-1][j]) || dp[i][j-2]) {
                        // 出现了 .* 或者 str[i] = 前一个位置的字符
                        // 就保留自身位置去匹配前一个位置
                        // 或者空串 去掉这两个位置 匹配当前位置
                        dp[i][j] = true;
                    }
                }


            }
        }

        // 确定 len1 * len2 的返回值
        return dp[len1][len2];
    }
}